此题有一个神仙结论:最优链上最多包含一个‘2’,且‘2’不能在链的两边。 至于证明过于简单但很麻烦(其实是我懒),给大家推荐一个博客,点这。
有了这个结论之后,我们就可以愉快的开始树形dp了。
我们用表示包含u节点的最长1链,表示包含u节点的含一个2,其余全是1的最长链。
那么,我们不难得到:
1.当u为1时,
2.当u为2时,
我们再用表示最大的的下标,表示次大的的下标,表示最大的的下标
每次更新时,维护上述3个值。
最后我们更新答案,可能会出现以下情况:
1.当u的值为1时
1.,说明最长的含2链包含了最长的1链,更新答案为
2.不存在该上关系但有含2,更新答案为
3.答案的链不含2,更新答案为
1.当u的值为2时
最长的含2链为
#include <cstdio>
#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;
#define LL long long
#define INF 1e15
const int MAXN = 1000000;
int n,a,b;
LL p = INF , q = 1 , Mag[ MAXN + 5 ];
vector< int > Graph[ MAXN + 5 ];
void update( LL a , LL b ) {
if( a * q < b * p ) p = a , q = b; //更新时为了避免除法,移项变为乘法
return;
}
LL f1[ MAXN + 5 ] , f2[ MAXN + 5 ];
void dfs( int u , int fa ) {
int f1_1 = 0 , f1_2 = 0 , f2_1 = 0;
if( Mag[ u ] == 1 ) f1[ u ] = 1;
if( Mag[ u ] == 2 ) f2[ u ] = 1;
for( int i = 0 ; i < Graph[ u ].size( ) ; i ++ ) {
int v = Graph[ u ][ i ];
if( v == fa ) continue;
dfs( v , u );
if( Mag[ u ] == 1 ) {
f1[ u ] = max( f1[ u ] , f1[ v ] + 1 );
f2[ u ] = max( f2[ u ] , f2[ v ] + 1 );
}
else if( Mag[ u ] == 2 )
f2[ u ] = max( f2[ u ] , f1[ v ] + 1 );
if( f1[ f1_1 ] < f1[ v ] ) {
f1_2 = f1_1;
f1_1 = v;
}
else if( f1[ f1_2 ] < f1[ v ] )
f1_2 = v;
if( f2[ f2_1 ] < f2[ v ] )
f2_1 = v;
}
if( Mag[ u ] == 1 ) {
if( f1_1 == f2_1 )
update( 2 , f1[ f1_2 ] + f2[ f2_1 ] + 1 );
else
update( 2 , f1[ f1_1 ] + f2[ f2_1 ] + 1 );
update( 1 , f1[ f1_1 ] + f1[ f1_2 ] + 1 );
}
if( Mag[ u ] == 2 )
update( 2 , f1[ f1_1 ] + f1[ f1_2 ] + 1 );
}
int main( ) {
scanf("%d",&n);
for( int i = 1 ; i <= n - 1 ; i ++ ) {
scanf("%d %d",&a,&b);
Graph[ a ].push_back( b );
Graph[ b ].push_back( a );
}
for( int i = 1 ; i <= n ; i ++ ) {
scanf("%lld",&Mag[ i ]);
p = min( Mag[ i ] , p );
}
dfs( 1 , 0 );
LL r = __gcd( p , q );
printf("%lld/%lld\n", p / r , q / r );
return 0;
}